package aco;

import aco.Ants.Ant;

import java.util.ArrayList;

// 用于ACS算法执行的线程类
public class VRPTW_ACS implements Runnable {

    private volatile boolean isRunning = true;

    private boolean threadRestarted;/* indicates whether the thread was restarted from outside */

    private VRPTW vrpInstance;

    public VRPTW_ACS(boolean threadRestarted, VRPTW vrp) {
        this.threadRestarted = threadRestarted;
        this.vrpInstance = vrp;
    }

    /**
     * 执行蚁群优化线程
     * do the work of running the ant colony which tries to solve the DVRPTW instance
     * using the available(known so far) customer requests
     */
    @Override
    public void run() {
        int counter = 0;
        isRunning = true;
        while (isRunning) {

            // 1.如果ACS线程不是首次开启，则需要根据上次运行的最优解，更新信息素
            // 【使用上次的全局最优蚂蚁，更新信息素】
            // the thread was restarted (i.e. it was previously stopped and started again)
            if (threadRestarted) {
                // compute the new value for the initial pheromone trail based on the current best solution so far
                int noAvailableNodes = vrpInstance.getIdAvailableRequests().size();
                Ants.trail_0 = 1. / ((double) (noAvailableNodes + 1) * (double) Ants.best_so_far_ant.total_tour_length);

                // preserve a certain amount of the pheromones from the previous run of the ant colony
                Ants.preservePheromones(vrpInstance);
            }

            // 2.构造蚁群 do the optimization task (work)
            construct_solutions(vrpInstance);
            InOut.noEvaluations++; // increase evaluations counter
            counter++;

            // 3.再次优化最优蚂蚁，并更新信息素
            update_statistics(vrpInstance); // local search 再次优化
            pheromone_trail_update(); // 最优蚂蚁更新信息素

            // 4.如果本次线程执行创建蚁群次数超过300，就中断优化
            // force the ant colony thread to stop its execution
            if (counter > 300) {
                isRunning = false;
            }
        }
    }

    /* 构造蚁群 */
    static void construct_solutions(VRPTW instance) {
        int k; /* counter variable */
        int step = 0; /* counter of the number of construction steps */
        int values[] = new int[2]; /* 存储最终的两个优化目标 */

        // 1.重置所有蚂蚁
        for (int i = 0; i < Ants.n_ants; i++) {
            Ants.ant_empty_memory(Ants.ants[i], instance);
        }

        // 2.每条路径都从仓库出发
        for (int i = 0; i < Ants.ants.length; i++) {
            for (int j = 0; j < Ants.ants[i].usedVehicles; j++) {
                Ants.ants[i].tours.get(j).add(-1);
            }
        }

        // 3.将已锁定节点加入到蚁群的路径中
        if (checkCommitedTours()) {
            for (int i = 0; i < Ants.n_ants; i++) {
                addCommitedNodes(Ants.ants[i], instance);
            }
        }

        // 4.蚁群处理可访问节点，利用 [joint mechanism]
        while (!isDone()) {
            for (int i = 0; i < Ants.n_ants; i++) {
                if (Ants.ants[i].toVisit > 0) {
                    // 4.1 [joint mechanism]
                    // choose for each ant in a probabilistic way by some type of roullette wheel selection
                    // which salesman to consider next, that will visit a city
                    values = Ants.neighbour_choose_and_move_to_next(Ants.ants[i], instance);

                    // 4.2 更新局部信息素 [local pheromone update rule]
                    if (values[0] != -1) {
                        Ants.local_acs_pheromone_update(Ants.ants[i], values[1]);
                    }
                }
            }
        }

        // 5.每条路径最终会到仓库
        double longestTourLength;
        int idLongestTour = 0;
        for (k = 0; k < Ants.n_ants; k++) {
            InOut.noSolutions++; // 找到解的数量+1
            longestTourLength = Double.MIN_VALUE;
            for (int i = 0; i < Ants.ants[k].usedVehicles; i++) {
                step = Ants.ants[k].tours.get(i).size();
                Ants.ants[k].tours.get(i).add(step, -1);

                Ants.ants[k].tour_lengths.set(i, VRPTW.compute_tour_length_(Ants.ants[k].tours.get(i)));
                Ants.ants[k].total_tour_length += Ants.ants[k].tour_lengths.get(i);
                if (longestTourLength < Ants.ants[k].tour_lengths.get(i)) {
                    longestTourLength = Ants.ants[k].tour_lengths.get(i);
                    idLongestTour = i;
                }
                // 更新这一步的信息素
                Ants.local_acs_pheromone_update(Ants.ants[k], i);
            }
            Ants.ants[k].longest_tour_length = longestTourLength;
            Ants.ants[k].indexLongestTour = idLongestTour;
            Ants.ants[k].costObjectives[0] = Ants.ants[k].total_tour_length;
            Ants.ants[k].costObjectives[1] = Ants.computeToursAmplitude(Ants.ants[k]);
        }
        InOut.n_tours += (Ants.n_ants * Ants.ants[0].usedVehicles); //each ant constructs a complete and closed tour
    }

    /**
     * check if there are any committed tours
     * (i.e. tours that contain at least one committed node that should be included in the ant's solution)
     */
    static boolean checkCommitedTours() {
        boolean result = false;
        int lastcommit;
        ArrayList<Integer> lastCommittedIndex = new ArrayList<>();
        for (int i = 0; i < Ants.best_so_far_ant.usedVehicles; i++) {
            lastcommit = Controller.getLastCommitedPos(i);
            lastCommittedIndex.add(lastcommit);
        }
        for (Integer a : lastCommittedIndex) {
            if (a > 0) {
                return true;
            }
        }
        return result;
    }

    /* 将当前已经锁定的城市，添加到蚂蚁a对应的各路径中 */
    static void addCommitedNodes(Ant a, VRPTW instance) {
        int index, city, current_city;
        double distance, arrivalTime, beginService;
        ArrayList<Request> reqList = instance.getRequests();
        int startIndex = 1, pos;

        // 创建链表lastCommitedIndexes。用于存储当前最优解的每条路径中，最后锁定的城市节点的位置。
        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int indexTour = 0; indexTour < Ants.best_so_far_ant.usedVehicles; indexTour++) {
            pos = Controller.getLastCommitedPos(indexTour);
            lastCommitedIndexes.add(pos);
        }

        // 处理所有路径
        for (int i = 0; i < lastCommitedIndexes.size(); i++) {
            // we have at least one committed node in the i-th tour (i.e. tour with index i)
            index = lastCommitedIndexes.get(i);
            if (index > 0) {
                // 1.add new (empty) tours in the ant's solution
                // if the number of vehicles (tours) from the ant solution is less than the index of the tour from the best so far solution
                // 这里为什么小于(i+1)而不是小于 i ，因为(a.usedVehicles)表示路径数量从1开始，而lastCommitedIndexes从0开始
                if (a.usedVehicles < (i + 1)) {
                    a.usedVehicles = i + 1;
                    for (int l = startIndex; l < a.usedVehicles; l++) {
                        a.tours.add(l, new ArrayList<Integer>());
                        a.tours.get(l).add(-1);
                        a.tour_lengths.add(l, 0.0);
                        a.currentQuantity.add(l, 0.0);
                        a.currentTime.add(l, 0.0);
                    }
                    startIndex = i + 1;
                }

                // 2.获取蚂蚁a路径i末端的城市编号current_city（其实这些蚂蚁都是重置后的，每条路径开始的位置是仓库）
                int lastPos = a.tours.get(i).size() - 1;
                current_city = a.tours.get(i).get(lastPos);
                current_city++; // 从路径取出来的城市编号是从 -1开始的，所以要+1

                // 3.将锁定城市节点，添加到蚂蚁a的路径i中
                // add in the ant's i-th tour all the committed nodes from the i-th tour of the best so far solution
                for (int j = 1; j <= index; j++) {
                    city = Ants.best_so_far_ant.tours.get(i).get(j);

                    // 3.1 判断是否满足时间窗约束（应该是不存在违反时间窗约束的情况）
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(i) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());
                    if (beginService > reqList.get(city + 1).getEndWindow()) {
                        System.out.println("Method addCommitedNodes: solution infeasible..");
                    }

                    // 3.2 add committed node to the ant's tour
                    a.tours.get(i).add(j, city);
                    a.visited[city] = true;
                    a.toVisit--;
                    a.currentTime.set(i, beginService);
                    a.beginService[city + 1] = beginService;
                    a.currentQuantity.set(i, a.currentQuantity.get(i) + reqList.get(city + 1).getDemand());

                    current_city = city + 1;
                }
            }

        }
    }

    /**
     * 判断蚁群中的每个蚂蚁是否处理完了所有的城市节点
     * check if there is still an ant with left cities to visit
     */
    static boolean isDone() {
        boolean done = true;
        for (int i = 0; i < Ants.n_ants; i++) {
            if (Ants.ants[i].toVisit > 0) {
                return false;
            }
        }
        return done;
    }

    /**
     * 初始化解，利用初始化的解计算初始信息素水平，并初始化蚁群信息素矩阵
     * initialize variables appropriately when starting a trial
     */
    static void init_try(VRPTW instance) {
        // 1. 初始化静态参数
        /* Initialize variables concerning statistics etc. */
        InOut.n_tours = 1;
        InOut.iteration = 1;
        Ants.best_so_far_ant.total_tour_length = Double.MAX_VALUE;
        Ants.restart_best_ant.total_tour_length = Double.MAX_VALUE;
        InOut.lambda = 0.05;

        // 2.初始化信息素矩阵
        int noAVailableNodes = instance.getIdAvailableRequests().size();
        if (noAVailableNodes == 0) {
            Ants.trail_0 = 1;
        } else {
            // 其中用到的 Ants.nn_tour() 方法是用来初始化解的
            Ants.trail_0 = 1. / ((double) (noAVailableNodes + 1) * (double) (Ants.nn_tour(instance)));
        }
        Ants.init_pheromone_trails(Ants.trail_0);
    }

    /**
     * relocate算子后，更新开始服务时间和当前时间
     * 更新源路径和目标路径的当前时间；更新两条路径，执行relocate操作的位置后面的城市序列的开始服务时间
     */
    static void updateBeginServiceRelocationMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        int currentCity, prevCity;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService = 0.0;
        ArrayList<Request> reqList = vrp.getRequests();
        int k = 0;
        // update of begin service times for the source tour
        for (int pos = i; pos < a.tours.get(indexTourSource).size() - 1; pos++) {
            k++;
            prevCity = a.tours.get(indexTourSource).get(pos - 1);
            currentCity = a.tours.get(indexTourSource).get(pos);
            if (pos == i) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Relocation Multiple indexTourSource: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourSource, beginService); // 路径末端城市的开始服务时间即为路径的当前时间

        // update of begin service times for the destination tour
        for (int pos = j; pos < a.tours.get(indexTourDestination).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            if (pos == j) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Relocation Multiple indexTourDestination: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourDestination, beginService);
    }

    /**
     * exchange算子后，更新开始服务时间和当前时间
     * 更新源路径和目标路径的当前时间；更新两条路径，执行exchange操作的位置后面的城市序列的开始服务时间
     */
    static void updateBeginServiceExchangeMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        int currentCity, prevCity;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService = 0.0;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.更新源路径
        for (int pos = i; pos < a.tours.get(indexTourSource).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourSource).get(pos - 1);
            currentCity = a.tours.get(indexTourSource).get(pos);
            if (pos == i) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Exchange Multiple indexTourSource: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourSource, beginService);

        // 2. 更新目标路径
        for (int pos = j; pos < a.tours.get(indexTourDestination).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            if (pos == j) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Exchange Multiple indexTourDestination: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourDestination, beginService);

    }

    /**
     * 检查relocate算子是否可行
     * 从indexTourSource路径中取出第i个城市插入到，indexTourDestination路径中第j个城市的位置，是否可行？？？
     */
    static boolean checkFeasibleTourRelocationMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        int city, previousCity, prevCity, nextCity, currentCity;
        double currentQuantity, arrivalTime, currentTime = 0.0, beginService, distance;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.检查汽车载量约束
        city = a.tours.get(indexTourSource).get(i);
        currentQuantity = a.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }
        // 2.检查时间窗约束
        // 2.1源路径的时间窗约束 [check time window constraints in source tour]
        for (int pos = i + 1; pos < a.tours.get(indexTourSource).size(); pos++) {
            if (pos == i + 1) { // 当验证紧挨取出城市后面的城市时
                prevCity = a.tours.get(indexTourSource).get(pos - 2);
                currentCity = a.tours.get(indexTourSource).get(pos);
                currentTime = a.beginService[prevCity + 1];
            } else { // 当验证其他城市时
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity+1).getServiceTime() + distance;
            beginService = Math.max(reqList.get(currentCity+1).getStartWindow(), arrivalTime);
            if (beginService > reqList.get(currentCity+1).getEndWindow()) {
                return false;
            }
        }
        // 2.2目标路径的时间窗约束 [check time window constraints in destination tour]
        // prevCity--->city
        previousCity = a.tours.get(indexTourDestination).get(j - 1);
        arrivalTime = a.beginService[previousCity+1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][city + 1];
        beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());
        if (beginService > reqList.get(city + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;
        // city--->nextCity
        nextCity = a.tours.get(indexTourDestination).get(j);
        arrivalTime = currentTime + reqList.get(city + 1).getServiceTime() + VRPTW.instance.distance[city + 1][nextCity + 1];
        beginService = Math.max(arrivalTime, reqList.get(nextCity + 1).getStartWindow());
        if (beginService > reqList.get(nextCity + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;
        // city--->...
        for (int pos = j + 1; pos < a.tours.get(indexTourDestination).size(); pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }
        return true;
    }

    /**
     * 检查exchange算子是否可行
     * 从indexTourSource路径中取出第i个城市插入到，indexTourDestination路径中第j个城市的位置，是否可行？？？
     */
    static boolean checkFeasibleTourExchangeMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        boolean isFeasible = true;
        int currentCity, prevCity, city1, city2;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService, currentQuantity;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.检查源路径和目标路径的载量限制 [check vehicle capacity tour constraints for source and destination tours]
        city1 = a.tours.get(indexTourSource).get(i);
        city2 = a.tours.get(indexTourDestination).get(j);
        currentQuantity = a.currentQuantity.get(indexTourSource) - reqList.get(city1 + 1).getDemand() + reqList.get(city2 + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }
        currentQuantity = a.currentQuantity.get(indexTourDestination) - reqList.get(city2 + 1).getDemand() + reqList.get(city1 + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }

        // 2.检查原路径的时间窗约束 [check feasibility for source tour regarding time windows constraints]
        for (int pos = i; pos < a.tours.get(indexTourSource).size(); pos++) {
            if (pos == i) {
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourDestination).get(j);
                currentTime = a.beginService[prevCity + 1];
            } else if (pos == (i + 1)) {
                prevCity = a.tours.get(indexTourDestination).get(j);
                currentCity = a.tours.get(indexTourSource).get(pos);
            } else {
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

        // 3.检查目标路径的时间窗约束 [check feasibility for destination tour regarding time windows constraints]
        for (int pos = j; pos < a.tours.get(indexTourDestination).size(); pos++) {
            if (pos == j) {
                prevCity = a.tours.get(indexTourDestination).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(i);
                currentTime = a.beginService[prevCity + 1];
            } else if (pos == (j + 1)) {
                prevCity = a.tours.get(indexTourSource).get(i);
                currentCity = a.tours.get(indexTourDestination).get(pos);
            } else {
                prevCity = a.tours.get(indexTourDestination).get(pos - 1);
                currentCity = a.tours.get(indexTourDestination).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

        return isFeasible;

    }

    /**
     * relocate算子（用于优化初始解）
     * skip committed (defined) nodes
     * relocateMultipleRouteIterated is performed multiple times until no further improvement
     * (which minimizes most the total traveled distance or reduces the number of used vehicles) is possible
     */
    static Ant relocateMultipleRouteIterated(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        boolean foundImprovement = true, isValid;
        int lastPos;
        double tempNo = Math.pow(10, 10);
        double round1, round2;

        // 1. 定义蚂蚁improvedAnt
        Ant improvedAnt = new Ant();
        improvedAnt.tours = new ArrayList();
        improvedAnt.tour_lengths = new ArrayList<Double>();
        improvedAnt.beginService = new double[VRPTW.n + 1];
        improvedAnt.currentTime = new ArrayList<Double>();
        improvedAnt.currentQuantity = new ArrayList<Double>();
        improvedAnt.usedVehicles = 1;
        for (int j = 0; j < improvedAnt.usedVehicles; j++) {
            improvedAnt.tours.add(j, new ArrayList<Integer>());
            improvedAnt.tour_lengths.add(j, 0.0);
        }
        improvedAnt.visited = new boolean[VRPTW.n];
        // the another node is the depot, which is by default visited by each salesman and added in its tour
        improvedAnt.toVisit = instance.getIdAvailableRequests().size();
        improvedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            improvedAnt.costObjectives[indexObj] = 0;
        }
        improvedAnt.earliestTime = new ArrayList(improvedAnt.usedVehicles);
        improvedAnt.latestTime = new ArrayList(improvedAnt.usedVehicles);

        // 2定义蚂蚁temp
        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        // 3.把蚂蚁a复制到，improvedAnt蚂蚁和temp蚂蚁
        Ants.copy_from_to(a, improvedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        // 4.获取每条路径的最后一个锁定节点的位置，作为relocate操作时每条路径开始的索引
        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        // 5.迭代搜索
        int count = 0; // 记录迭代次数
        while (foundImprovement) { // 是否还存在优化空间
            foundImprovement = false;
            count++;
            if (count > 100) {
                System.out.println("Inside relocateMultipleRouteIterated; count=" + count);
            }
            Ants.copy_from_to(improvedAnt, a, instance);
            Ants.copy_from_to(improvedAnt, temp, instance);

            // 遍历每条可能的源路径和目标路径
            for (int indexTourSource = 0; indexTourSource < temp.usedVehicles; indexTourSource++) {
                for (int indexTourDestination = 0; indexTourDestination < temp.usedVehicles; indexTourDestination++) {
                    if (indexTourSource != indexTourDestination) {
                        // index of the element to be moved/relocated
                        if (indexTourSource > lastCommitedIndexes.size() - 1) {
                            startIndexSource = 1;
                        } else {
                            startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                        }

                        // index of the relocation's destination
                        if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                            startIndexDestination = 1;
                        } else {
                            startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                        }

                        // 遍历源路径和目标路径的每个位置
                        for (int i = startIndexSource; i < temp.tours.get(indexTourSource).size() - 1; i++) {
                            for (int j = startIndexDestination; j < temp.tours.get(indexTourDestination).size(); j++) {
                                // check if results a feasible solution (i.e. no time window constraint is violated)
                                feasible = checkFeasibleTourRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                                if (feasible) {
                                    // obtain the neighbour solution corresponding to the relocation operator
                                    city = temp.tours.get(indexTourSource).get(i);
                                    temp.tours.get(indexTourSource).remove(i);
                                    temp.tours.get(indexTourDestination).add(j, city);

                                    newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city + 1).getDemand();
                                    temp.currentQuantity.set(indexTourSource, newQuantity1);
                                    newQuantity2 = temp.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
                                    temp.currentQuantity.set(indexTourDestination, newQuantity2);

                                    // update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                    // also update the current time of the source and destination tours
                                    updateBeginServiceRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

                                    // update total traveled distance and lengths of source and destination tours
                                    sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                    sourceNextCity = temp.tours.get(indexTourSource).get(i);
                                    newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city + 1] - VRPTW.instance.distance[city + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][sourceNextCity + 1];

                                    destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                    destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                    newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city + 1] + VRPTW.instance.distance[city + 1][destinationNextCity + 1];

                                    newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                    temp.total_tour_length = newTotalDistance;
                                    temp.tour_lengths.set(indexTourSource, newDistance1);
                                    temp.tour_lengths.set(indexTourDestination, newDistance2);

                                    // if the source tour becomes empty (no city is visited except the depot), remove this empty tour
                                    if (temp.tours.get(indexTourSource).size() == 2 && temp.tours.get(indexTourSource).get(0) == -1 && temp.tours.get(indexTourSource).get(1) == -1) {
                                        temp.tours.remove(indexTourSource);
                                        temp.tour_lengths.remove(indexTourSource);
                                        temp.currentQuantity.remove(indexTourSource);
                                        temp.currentTime.remove(indexTourSource);
                                        temp.usedVehicles--;
                                    }

                                    // performing the rounding of the two numbers up to 10 decimals so that in the
                                    // comparison of the 2 double values to consider only the first 10 most significant decimals
                                    round1 = Math.round(temp.total_tour_length * tempNo) / tempNo;
                                    round2 = Math.round(improvedAnt.total_tour_length * tempNo) / tempNo;
                                    //if some improvement is obtained in the total traveled distance
                                    // 注意优先级：车辆数量>总路程长度
                                    if (((round1 < round2) && (temp.usedVehicles == improvedAnt.usedVehicles))
                                            || (temp.usedVehicles < improvedAnt.usedVehicles)) {
                                        Ants.copy_from_to(temp, improvedAnt, instance);
                                        foundImprovement = true;
                                    }

                                    // restore previous solution constructed by ant
                                    Ants.copy_from_to(a, temp, instance);
                                }
                            }
                        }
                    }
                }
            }
        }
        return improvedAnt;
    }

    /**
     * exchange算子（用于优化初始解）
     */
    static Ant exchangeMultipleRouteIterated(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city1, city2, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        boolean foundImprovement = true;
        int lastPos;
        double tempNo = Math.pow(10, 10);
        double round1, round2;

        // 1.初始化improvedAnt，作为优化后的蚂蚁（解）
        Ant improvedAnt = new Ant();
        improvedAnt.tours = new ArrayList();
        improvedAnt.tour_lengths = new ArrayList<Double>();
        improvedAnt.beginService = new double[VRPTW.n + 1];
        improvedAnt.currentTime = new ArrayList<Double>();
        improvedAnt.currentQuantity = new ArrayList<Double>();
        improvedAnt.usedVehicles = 1;
        for (int j = 0; j < improvedAnt.usedVehicles; j++) {
            improvedAnt.tours.add(j, new ArrayList<Integer>());
            improvedAnt.tour_lengths.add(j, 0.0);
        }
        improvedAnt.visited = new boolean[VRPTW.n];
        // the another node is the depot, which is by default visited by each salesman and added in its tour
        improvedAnt.toVisit = instance.getIdAvailableRequests().size();
        improvedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            improvedAnt.costObjectives[indexObj] = 0;
        }
        improvedAnt.earliestTime = new ArrayList(improvedAnt.usedVehicles);
        improvedAnt.latestTime = new ArrayList(improvedAnt.usedVehicles);

        // 2.初始化temp，作为中间变量的蚂蚁（解）
        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        // the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        // 3.把蚂蚁a复制到，improvedAnt蚂蚁和temp蚂蚁
        Ants.copy_from_to(a, improvedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        // 4.获取每条路径的最后一个锁定节点的位置，作为relocate操作时每条路径开始的索引
        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        int count = 0;
        while (foundImprovement) {
            foundImprovement = false;

            count++;
            if (count > 100) {
                System.out.println("Inside exchangeMultipleRouteIterated; count=" + count);
            }

            Ants.copy_from_to(improvedAnt, a, instance);
            Ants.copy_from_to(improvedAnt, temp, instance);

            for (int indexTourSource = 0; indexTourSource < (temp.usedVehicles - 1); indexTourSource++) {
                for (int indexTourDestination = indexTourSource + 1; indexTourDestination < temp.usedVehicles; indexTourDestination++) {
                    if (indexTourSource != indexTourDestination) {
                        //index of the element to be moved from the source tour
                        if (indexTourSource > lastCommitedIndexes.size() - 1) {
                            startIndexSource = 1;
                        } else {
                            startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                        }

                        //index of the element to be moved from the destination tour
                        if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                            startIndexDestination = 1;
                        } else {
                            startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                        }
                        for (int i = startIndexSource; i < temp.tours.get(indexTourSource).size() - 1; i++) {
                            for (int j = startIndexDestination; j < temp.tours.get(indexTourDestination).size() - 1; j++) {
                                if (indexTourSource <= indexTourDestination) {
                                    // check if results a feasible solution (i.e. no time window constraint is violated)
                                    feasible = checkFeasibleTourExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                                    if (feasible) {
                                        // obtain the neighbour solution corresponding to the relocation operator
                                        city1 = temp.tours.get(indexTourSource).get(i);
                                        city2 = temp.tours.get(indexTourDestination).get(j);
                                        temp.tours.get(indexTourSource).set(i, city2);
                                        temp.tours.get(indexTourDestination).set(j, city1);


                                        newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city1 + 1).getDemand() + reqList.get(city2 + 1).getDemand();
                                        temp.currentQuantity.set(indexTourSource, newQuantity1);
                                        newQuantity2 = temp.currentQuantity.get(indexTourDestination) - reqList.get(city2 + 1).getDemand() + reqList.get(city1 + 1).getDemand();
                                        temp.currentQuantity.set(indexTourDestination, newQuantity2);

                                        // update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                        // also update the current time of the source and destination tours
                                        updateBeginServiceExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

                                        // update total traveled distance and lengths of source and destination tours
                                        sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                        sourceNextCity = temp.tours.get(indexTourSource).get(i + 1);
                                        newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city1 + 1] - VRPTW.instance.distance[city1 + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][city2 + 1] + VRPTW.instance.distance[city2 + 1][sourceNextCity + 1];

                                        destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                        destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                        newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][city2 + 1] - VRPTW.instance.distance[city2 + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city1 + 1] + VRPTW.instance.distance[city1 + 1][destinationNextCity + 1];

                                        newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                        temp.total_tour_length = newTotalDistance;
                                        temp.tour_lengths.set(indexTourSource, newDistance1);
                                        temp.tour_lengths.set(indexTourDestination, newDistance2);

                                        // performing the rounding of the two numbers up to 10 decimals so that in the
                                        // comparison of the 2 double values to consider only the first 10 most significant decimals
                                        round1 = Math.round(temp.total_tour_length * tempNo) / tempNo;
                                        round2 = Math.round(improvedAnt.total_tour_length * tempNo) / tempNo;
                                        // if some improvement is obtained in the total traveled distance
                                        if (round1 < round2) {
                                            Ants.copy_from_to(temp, improvedAnt, instance);
                                            foundImprovement = true;
                                        }
                                        // restore previous solution constructed by ant
                                        Ants.copy_from_to(a, temp, instance);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return improvedAnt;
    }

    /* 将编号为city的城市放在路径indexSalesman末端是否可行？ */
    static boolean isFeasible(VRPTW vrp, Ant a, int city, double beginService, double beginServiceDepot, int indexSalesman) {
        boolean ok = false;
        double currentQuantity;
        ArrayList<Request> reqList = vrp.getRequests();
        // check
        currentQuantity = a.currentQuantity.get(indexSalesman) + reqList.get(city).getDemand();
        if (beginService <= reqList.get(city+1).getEndWindow() // upper bound of the time window of the next customer to be visited
                && currentQuantity <= vrp.getCapacity() // current capacity of the car
                && beginServiceDepot <= reqList.get(0).getEndWindow()) { // vehicle arrival time at the depot (the maximum total route time -> upper bound of the time window of the depot)
            ok = true;
        }
        return ok;
    }

    /**
     * 对当前最优解进行优化 [relocate][exchange]
     * manage some statistical information about the trial, especially if a new best solution (best-so-far) is found
     * and adjust some parameters if a new best solution is found
     */
    static void update_statistics(VRPTW instance) {
        int iteration_best_ant;
        Object obj = new Object();
        double round1, round2;
        double tempNo = Math.pow(10, 10);

        // 1.获取当前最优蚂蚁a（当前最优解的）
        /* iteration_best_ant is a global variable */
        iteration_best_ant = Ants.find_best();
        Ant a = Ants.ants[iteration_best_ant];

        // 2.local search
        a = relocateMultipleRouteIterated(a, instance);
        a = exchangeMultipleRouteIterated(a, instance);

        // 3.使用再次优化后得到的a，以一定的概率，更新当前最优解（此处使用了线程互斥锁）
        synchronized (obj) {
            round1 = Math.round(a.total_tour_length * tempNo) / tempNo;
            round2 = Math.round(Ants.best_so_far_ant.total_tour_length * tempNo) / tempNo;
            if ((a.usedVehicles < Ants.best_so_far_ant.usedVehicles) // 使用车辆数量的优势
                    || ((a.usedVehicles == Ants.best_so_far_ant.usedVehicles) && (round1 < round2)) // 车辆数量相等时，以一定概率接受a
                    || ((round1 < round2) && (Ants.best_so_far_ant.total_tour_length == Double.MAX_VALUE))) {
                Ants.copy_from_to(a, Ants.best_so_far_ant, instance);
            }
        }
    }

    /**
     * 更新全局信息素
     * manage global Ants.pheromone trail update for the ACO algorithms
     */
    static void pheromone_trail_update() {
        Ants.global_acs_pheromone_update(Ants.best_so_far_ant);
    }

    // 使蚁群系统结束执行
    public void terminate() {
        isRunning = false;
    }
}